#include <iostream>

class MyLinkedList 
{
public:
    struct ListNode
    {
        int val;
        ListNode * next;
        ListNode(int x) : val(x), next(nullptr)
        {}
    };

    int _size;
    ListNode * _dummyHead;
    
    MyLinkedList() 
    {
        _dummyHead = new ListNode(0);
        _size = 0;
    }
    
    int get(int index) 
    {
        if(index < 0 || index >= _size)
        {
            return -1;
        }
        ListNode * cur = _dummyHead->next;
        for(int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) 
    {
        ListNode * newNode = new ListNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size ++;
    }
    
    void addAtTail(int val) 
    {
        ListNode * newNode = new ListNode(val);
        ListNode * cur = _dummyHead;
        for(int i = 0; i < _size; i++)
        {
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
    
    void addAtIndex(int index, int val) 
    {
        if(index > _size)
        {
            return;
        }
        else if(index < 0)
        {
            index = 0;
        }
        ListNode * newNode = new ListNode(val);
        ListNode * cur = _dummyHead;
        for(int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) 
    {
        if(index >= _size || index < 0)
        {
            return;
        }
        ListNode * cur = _dummyHead;
        for (int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        ListNode * tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        _size--;
    }
};


int main() {
    // 测试用例1
    MyLinkedList linkedList1;
    linkedList1.addAtHead(1);
    linkedList1.addAtTail(3);
    linkedList1.addAtIndex(1, 2);   // 链表变为 1->2->3
    std::cout << "Test Case 1:" << std::endl;
    std::cout << "get(1): " << linkedList1.get(1) << std::endl; // 返回 2
    linkedList1.deleteAtIndex(1);   // 现在链表是 1->3
    std::cout << "get(1): " << linkedList1.get(1) << std::endl; // 返回 3

    // 测试用例2
    MyLinkedList linkedList2;
    linkedList2.addAtHead(5);
    linkedList2.addAtHead(2);
    linkedList2.addAtTail(9);
    linkedList2.addAtIndex(2, 7);   // 链表变为 2->5->7->9
    std::cout << "Test Case 2:" << std::endl;
    for (int i = 0; i < 4; ++i) {
        std::cout << "get(" << i << "): " << linkedList2.get(i) << std::endl;
    }
    linkedList2.deleteAtIndex(0);   // 删除头节点，链表变为 5->7->9
    std::cout << "After deleteAtIndex(0):" << std::endl;
    for (int i = 0; i < 3; ++i) {
        std::cout << "get(" << i << "): " << linkedList2.get(i) << std::endl;
    }
    return 0;
}
